#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-11-20 9:56 上午
# @Author  : yangdy
# @File    : 2020-11-20.147.对链表进行插入排序
# @Software: PyCharmCE
from tools.my_methods import *


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        display_list(head)
        ans, p = None, head
        while p:
            x, y = None, ans
            while y and y != p and y.val < p.val:
                x, y = y, y.next
            # u = ListNode(p.val)
            # if x is None:
            #     ans, u.next = u, y
            # else:
            #     x.next, u.next = u, y
            q = p.next
            if x is None:
                ans = p
                p.next = y
            else:
                x.next = p
                p.next = y
            p = q
        display_list(ans)
        return ans


questions = [
    ([4, 2, 1, 3],),
    ([-1, 5, 3, 4, 0],),
]

work(questions, lambda q: Solution().insertionSortList(mk_list(q[0], ListNode)))
